package algorithm.middle;

import java.util.Arrays;

/**
 * @BelongsProject: LeetCode
 * @BelongsPackage: algorithm.middle
 * @Author: 江岸
 * @CreateTime: 2021-05-05 18:29
 * @Description: 给你一个整数数组 nums ，你可以对它进行一些操作。
 *
 * 每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除每个等于 nums[i] - 1 或 nums[i] + 1 的元素。
 *
 * 开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：nums = [3,4,2]
 * 输出：6
 * 解释：
 * 删除 4 获得 4 个点数，因此 3 也被删除。
 * 之后，删除 2 获得 2 个点数。总共获得 6 个点数。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/delete-and-earn
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class DeleteAndEarn740 {
    //使用打家劫舍的思路 动态规划
    public int deleteAndEarn(int[] nums) {
        if (nums.length==1) return nums[0];
        int max = Arrays.stream(nums).max().getAsInt();
        int[] arr = new int[max];
        for (int x:nums){
            arr[x-1] = arr[x-1] +1;
        }
        int[] dp = new int[max];
        dp[0] = arr[0];
        dp[1] =  Math.max(dp[0],2*arr[1]);
        for (int i=2;i<arr.length;i++){
            dp[i] = Math.max(dp[i-1],dp[i-2]+(i+1)*arr[i]);
        }
        return dp[max-1];
    }
    /**
     * 我们在原来的 nums 的基础上构造一个临时的数组 all，这个数组，以元素的值来做下标，下标对应的元素是原来的元素的个数。
     *
     * 举个例子：
     *
     * nums = [2, 2, 3, 3, 3, 4]
     *
     * 构造后：
     *
     * all=[0, 0, 2, 3, 1];
     *
     * 就是代表着 22 的个数有两个，33 的个数有 33 个，44 的个数有 11 个。
     *
     * 其实这样就可以变成打家劫舍的问题了呗。
     *
     * 我们来看看，打家劫舍的最优子结构的公式：
     *
     * dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
     *
     * 再来看看现在对这个问题的最优子结构公式：
     *
     * dp[i] = Math.max(dp[i - 1], dp[i - 2] + i * all[i]);
     *
     * 作者：fakerleet
     * 链接：https://leetcode-cn.com/problems/delete-and-earn/solution/ru-guo-ni-li-jie-liao-da-jia-jie-she-zhe-ti-ni-ken/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
}
